package linkedlist.leetcode_25_hard;


public class ReverseKGroupDeBug {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        new ReverseKGroupDeBug().reverseKGroup(head,2);
    }
    /**
     * K个一组翻转链表
     * @param head  给定链表头节点
     * @param k     每K个翻转
     * @return      返回翻转后的链表头
     *
     * 就是翻转链表加了一些限制条件，然而就是限制条件最恶心
     *
     * 每K个一组，可以循环K次，找到这K个节点的尾，然后对K个链表翻转。
     *      k = 2； 1 - 2 - 3 - 4 - 5
     * 需要注意的几个点：
     *      1. 翻转一组后要连接 下一组的头 比如第一组翻转后 2 - 1 ，连接下一组 2 - 1 - 3 - 4
     *          需要连接下一组的头，就要记录
     *      2. 不够k个节点的部分 保持原来的顺序 2 - 1 - 4 - 3 - 5; 那么就需要判断够不够k个节点
     *
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || k <= 0 ){
            return null;
        }
        //利用哑节点进行返回
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        //pre用来连接节点
        ListNode pre = dummyNode;
        //开始和结尾
        ListNode start = head;
        ListNode end = head;


        while(end != null) {
            //找到尾节点，注意循环的终止条件， i < k -1 时，end刚好停留在尾节点
            //因为从head出发。
            for (int i = 0; end != null && i < k - 1; i++) {
                end = end.next;
            }
            //还未走完k步就为null了，说明不够k个节点，保留原顺序就可以了
            if (end == null) {
                break;
            }
            //记录下一组的头节点
            ListNode nextHead = end.next;
            //断链
            end.next = null;
            //翻转
            pre.next = reverse(start);
            //翻转完了要连接下一组
            start.next = nextHead;
            //注意这里，连接时，都要用当前这k个节点的尾节点 去连接下一组的头，每一次都要更新pre指针去连接
            pre = start;

            //下一组开始同样的过程
            start = nextHead;
            end = nextHead;
        }
        //利用哑节点进行返回
        return dummyNode.next;
    }
    public ListNode reverse(ListNode head){
        ListNode pre = null;
        while(head != null){
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}
